#include<stdio.h>
#define SWAP( a , b )				\
	do{					\
		typeof(a) _tmp = (a);		\
		(a) = (b);			\
		(b) = _tmp;			\
	}while(0)

#define QUICK_SORT( TYPE , ARRAY , NUM )				\
{									\
	void quicksort_##TYPE( TYPE * _ARRAY , unsigned int num ){	\
		unsigned int left  = 1 , right = num -1;		\
		if( num < 2 ){						\
			return ;					\
		}							\
									\
		TYPE pivot = _ARRAY[0];					\
									\
		while(1){						\
			while( left<right && _ARRAY[right] >= pivot ){	\
				right -- ;				\
			}						\
			while( left<right && _ARRAY[left] < pivot ){	\
				left++;					\
			}						\
									\
			if( left == right ){				\
				break;					\
			}						\
			SWAP( _ARRAY[left] , _ARRAY[right] );		\
		}							\
		if( _ARRAY[left] < pivot ){				\
			SWAP( _ARRAY[0] , _ARRAY[left] );		\
		}else{							\
			left = 0;					\
		}							\
									\
		quicksort_##TYPE( _ARRAY , left);			\
		quicksort_##TYPE( _ARRAY+left+1 , num-left-1);		\
 									\
		return;							\
	}								\
	quicksort_##TYPE( ARRAY , NUM ) ; 				\
}
	
#ifdef _UNIT_TEST_
int main(){

	#define COUNT 100

	srandom(time(NULL));
	int array[ COUNT ];
	int i;
	for( i=0 ; i<COUNT ;i++){
		array[i] = random();
		srandom(array[i]);
	}

	QUICK_SORT( int , array , COUNT );
	QUICK_SORT( int , array , COUNT );
	
	return 0;
}
#endif
